#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

/*HJJ QQ479287006
 *给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

 

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

int searchInsert(vector<int> &nums, int target) {


    int low = 0;
    int high = nums.size() - 1;
    int mid;
    while (low <= high)//小于等于
    {
        mid = low + (high - low) / 2;

        if (nums[mid] > target) {
            high = mid - 1;
        }
        if (nums[mid] < target) {
            low = mid + 1;
        } else if (nums[mid] == target) {
            return mid;
        }
    }


//    while ((low<=nums.size()-1) && nums[low]<target )
//    {
//        low++;
//    }

    return high + 1;

}